package problem474;

//474.一和零
//https://leetcode.cn/problems/ones-and-zeroes/description/

// class Solution {
//     public int findMaxForm(String[] strs, int m, int n) {
//         int len = strs.length;
//         int[][][] dp = new int[len+1][m+1][n+1];
       
//         for(int k = 1; k<=len; k++) {
//             //计算字符串中0,1出现的个数
//             int x0 = 0, x1 = 0;
//             for(char ch:strs[k-1].toCharArray()) {
//                 if(ch == '0') x0++;
//                 else x1++;
//             }
//             for(int i = 0; i<=m; i++) {
//                 for(int j = 0; j<=n; j++) {
//                     dp[k][i][j] = dp[k-1][i][j];
//                     if(i - x0 >= 0 && j-x1 >= 0) dp[k][i][j] = Math.max(dp[k][i][j], dp[k-1][i-x0][j-x1]+1); 
//                 }
//             }
//         }
//         return dp[len][m][n];
//     }
// }

/*
dp[k][i][j]:从前k个字符串中挑选, 0的个数不超过i, 1的个数不超过j, 的最大子集

*/

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m+1][n+1];
       
        for(int k = 1; k<=len; k++) {
            //计算字符串中0,1出现的个数
            int x0 = 0, x1 = 0;
            for(char ch:strs[k-1].toCharArray()) {
                if(ch == '0') x0++;
                else x1++;
            }
            for(int i = m; i>=x0; i--) {
                for(int j = n; j>=x1; j--) {
                   dp[i][j] = Math.max(dp[i][j], dp[i-x0][j-x1]+1); 
                }
            }
        }
        return dp[m][n];
    }
}